This invention relates to a first in, first out (FIFO) memory system. More particularly, this invention relates to a method and structure for controlling an asynchronous FIFO memory system, and for determining the amount of data currently stored in a FIFO memory of the asynchronous FIFO memory system.
Data values sequentially written to a memory of a FIFO memory system are sequentially read from the memory in a first in, first out manner. Most FIFO memory systems are implemented with random access memories having two separate address counters. One address counter is used to maintain a current read address and the other counter is used to maintain a current write address. A FIFO memory system in which both the read address counter and the write address counter are clocked by the same clock signal is referred to as a xe2x80x9csynchronousxe2x80x9d FIFO memory system. In contrast, a FIFO memory system in which the read address counter and the write address counter are clocked by different clock signals is referred to as an xe2x80x9casynchronousxe2x80x9d FIFO memory system.
In both synchronous and asynchronous FIFO systems, both the read and write address counters are circular counters that wrap around to an initial address after a last address is accessed. The read and write address counter output signals are either multiplexed to address a single-port random access memory (RAM), or they are separately provided to address different input ports of a multi-port RAM (e.g., a dual-port RAM). In either scheme, two extreme conditions, namely FIFO EMPTY and FIFO FULL, must be detected to ensure proper operation of the FIFO memory system. The FIFO EMPTY condition must be detected so that read operations from the memory can be prevented during the time that the memory is empty (since there are no valid data values present in the memory to read). The FIFO FULL condition must be detected so that write operations to the memory can be prevented during the time that the memory is full (since there is no memory space present in the memory to store any additional data values).
The contents of the read and write address counters are typically used to determine whether the memory is empty or full. To do this, the contents of the read and write address counters are compared. If the contents of the read address counter are identical to the contents of the write address counter, the memory is either empty or full. However, identifying that the contents of the read address counter and the write address counter are identical, by itself, does not distinguish whether the memory is empty or full. That is, the contents of the read address counter are identical to the contents of the write address counter when the memory is empty, and also when the memory is full.
One conventional method used to determine whether the memory is empty or full is to detect what type of operation caused the contents of the read and write address counters to match. If a read operation was performed (i.e., the read address counter was incremented), the resulting equality of the read and write address counters indicates a FIFO EMPTY condition. Conversely, if a write operation was performed (i.e., the write address counter was incremented), the resulting equality of the read and write address counters indicates a FIFO FULL condition. However, determining the type of operation that caused the contents of the read and write address counters to match can become complicated, particularly when the read and write address counters are clocked asynchronously.
Another prior art system subtracts the contents of the read and write address counters to determine when the read address is within one address of catching up to the write address and when the write address is within one address of catching up to the read address. Again, the subtraction circuitry for such a system is unreliable when the read and write address counters are clocked asynchronously.
Yet another prior art system, disclosed in co-owned U.S. Pat. No. 5,898,893, includes a direction circuit and a control circuit for generating FIFO FULL and FIFO EMPTY command signals. (U.S. Pat. No. 5,898,893 is hereby incorporated by reference.) The circular sequences of the write address and read address are divided into segments, and portions of the write address and read address are encoded to indicate the segments in which the current read address and current write address are located within their respective circular sequences. The direction circuit is connected to receive the encoded portions of the read and write addresses. In response, the direction circuit generates a DIRECTION signal that is set to a first state when the read address is in the segment prior to the segment of the write address, and is set to a second state when the write address is in the segment prior to the segment of the read address. The DIRECTION signal is used to determine whether the FIFO memory is empty or full when the read address equals the write address.
In addition to FIFO FULL and FIFO EMPTY conditions, it is also valuable for a FIFO memory system to generate status information regarding the amount of occupied memory at any point in time. For example, some users require status information to control burst read or write operations when the memory is half-full or half-empty. Such status information is relatively easy to obtain in synchronous systems by subtracting a currently-generated binary read address signal from a currently-generated binary write address signal. However, status information is much more difficult to obtain in asynchronous FIFO memory systems because of the danger of xe2x80x9cglitchesxe2x80x9d (i.e., momentary erroneous values produced when an address counter increments from an initial value to a next-sequential value). Because the read and write clock signals are asynchronous, if the subtraction operation is clocked by the write clock signal, there is a danger that glitches in the read address can produce erroneous subtraction results. Conversely, if the subtraction operation is clocked by the read clock signal, there is a danger of glitches in the write address at the moment that the subtraction operation is performed.
Status information can be derived in an asynchronous system using the encoded portions of the write address and read address taught in co-owned U.S. Pat. No. 5,898,893, but this derived status information would be inaccurate and unreliable under certain conditions, and therefore not very useful to a user under those conditions.
It would therefore be desirable to have a reliable structure and method for detecting full and empty conditions of a FIFO that overcome the problems associated with the conventional structures, described above. It would also be desirable to have a reliable and accurate structure and method for determining the amount of data stored in asynchronous FIFO memories.
The present invention provides a reliable and robust structure and method for controlling an asynchronous FIFO memory system, and for accurately determining the amount of data stored in the FIFO memory system. Unlike prior art FIFO memory systems, the present invention sacrifices one memory location to simplify the full/empty determination process (i.e., a FULL control signal is generated when the current binary write address is one memory location behind the current binary read address, thereby preventing the write address counter from xe2x80x9ccatching upxe2x80x9d to the read address counter). In addition, unlike prior art asynchronous FIFO memory systems, the present invention provides accurate information regarding the amount of data currently stored in the FIFO memory by synchronizing a current read address to the write clock, thereby providing reliable information that can be used to determine the current capacity of the FIFO memory without the danger of errors caused by glitches.
The present FIFO memory system includes a memory, a write address counter, a read address counter, a flag control circuit for generating FULL and EMPTY command signals, and an optional status control circuit for generating a FIFO status signal indicating the amount of data stored in the FIFO memory at a given moment during operation. The write address counter and read address counter generate an incrementing binary write address and an incrementing binary read address, respectively, that change in accordance with a predetermined circular binary counting sequence. A currently-generated binary write address signal is transmitted to the memory under the control of a WRITE_ALLOW control signal and a write clock signal during write operations, and a currently-generated binary read address is transmitted to the memory under the control of a READ_ALLOW control signal and a read clock signal during read operations. The WRITE_ALLOW and READ_ALLOW control signals are generated based on the FULL and EMPTY control signals generated by the flag control circuit.
In accordance with a first aspect of the present invention, the flag control circuit includes a read address register section, a write address register section, and a comparator circuit. The read address register section includes a binary-to-Gray-code converter for converting the current binary read address generated by the read address counter into a series of sequential Gray-code read address values that include a next-to-be-used read address value, a current read address value, and a last-used read address value. Similarly, the write address register includes a binary-to-Gray-code converter for converting the current binary write address generated by the write address counter into a series of sequential Gray-code write address values that include a next-to-be-used write address value and a current write address value. The comparator circuit compares selected pairs of Gray-code read address values and Gray-code write address values, and generates the FULL and EMPTY control signals based on these comparisons. In particular, the comparator circuit generates the EMPTY control signal when the current write address value is equal to the current read address value. In contrast, the comparator circuit generates the FULL control signal when the current write address value is equal to the last-used read address value, thereby preventing the write address counter from xe2x80x9ccatching upxe2x80x9d to the read address counter. By preventing the write address counter from xe2x80x9ccatching upxe2x80x9d to the read address counter, the determination of the FULL and EMPTY conditions is greatly simplified, thereby providing a reliable and robust structure and method for controlling a FIFO memory system.
In accordance with a second aspect of the present invention, a status control circuit synchronizes the current binary read address generated by the read address counter to the write clock, and then subtracts the write-synchronized binary read address from the current binary write address to determine the amount of data stored in the memory. The status control circuit includes a binary-to-Gray-code converter for converting the binary read address to a Gray-code read address, a write-synchronization register for synchronizing the Gray-code read address to the write clock, a Gray-code-to-binary converter for reconverting the Gray-code read address to form the write-synchronized binary read address, and a subtractor for determining a difference between the binary write address received from the write address counter and the write-synchronized binary read address. By generating the write synchronized read address in binary form, the difference between the currently-generated binary read and write addresses is readily determined, thereby providing an accurate indication of the amount of data stored in the memory. By converting the addresses to Gray-code format (in which only one bit changes between successive count values) the values can be compared without generating glitches in the comparison results.
The present FIFO memory system can be implemented, e.g., by a field programmable gate array or any other type of integrated circuit chip.